class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hashset;
        for (auto n : wordList) hashset.insert(n);
        vector<vector<string>> res{};
        if(hashset.find(endWord) == hashset.end()) return res;
        queue<vector<string>> memo;
        memo.push({beginWord});
        int step = 0;
        while(!memo.empty())
        {
            step++;
            int count = memo.size();
            set<string> to_delete;
            while(count--)
            {
                string s = memo.front().back();
                for(int i = 0; i < s.length(); i++)
                {
                    char ori = s[i];
                    bool flag = false;
                    for(char c = 'a'; c <= 'z'; c++)
                    {
                        s[i] = c;
                        if(s == endWord)
                        {
                            memo.front().push_back(s);
                            res.push_back(memo.front());
                            flag = true;
                            break;
                        }
                        auto it = hashset.find(s);
                        if(it != hashset.end())
                        {
                            auto vec = memo.front();
                            vec.push_back(s);
                            memo.push(vec);
                            to_delete.insert(s);
                        }
                    }
                    if(flag) break;
                    s[i] = ori;
                }
                
                memo.pop();
            }
            for(auto n : to_delete) hashset.erase(hashset.find(n));
            if(!res.empty()) break;
        }
        return res;
    }
};
